package com.LeetCode.Graph;

import org.junit.Test;

import java.util.*;

/**
 * 单词接龙
 */
public class HitWord {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if(wordList.size() == 0 || !wordSet.contains(endWord))
            return 0;

        wordSet.remove(beginWord);

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);

        int wordLen = beginWord.length();
        int step = 1;

        while(!queue.isEmpty()){
            int curSize = queue.size();
            for(int i = 0; i<curSize; i++){
                String word = queue.poll();
                char[] charArray = word.toCharArray();

                for(int j = 0; j<wordLen; j++){
                    char originalChar = charArray[j];

                    for(int k = 'a'; k <= 'z'; k++){
                        if(k == originalChar){
                            continue;
                        }

                        charArray[j] = (char)k;
                        String nextWord = String.valueOf(charArray);

                        if(wordSet.contains(nextWord)){
                            if(nextWord.equals(endWord)){
                                return step + 1;
                            }

                            if(!visited.contains(nextWord)){
                                queue.add(nextWord);
                                visited.add(nextWord);
                            }
                        }
                    }
                    charArray[j] = originalChar;
                }
            }
            step++;
        }
        return 0;
    }

    @Test
    public void test(){
        String begin = "hit";
        String end = "cog";
        String[] words1 = {"hot","dot","dog","lot","log"};
        String[] words2 = {"hot","dot","dog","lot","log","cog"};
        System.out.println(ladderLength(begin,end,new ArrayList<>(Arrays.asList(words2))));
    }


}
